import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/2 10:20
 * @description 这类问题中，如果回溯看成一颗树的话，从根到叶子节点内的元素是可以重复的，为一个子集，但是相同数层的元素不能重复，即树枝可以重复，树层不能重复。
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int[] nums = {1, 2, 2};
        solution2.subsetsWithDup(nums);
    }
    List<Integer> t = new ArrayList<>();
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs( 0, nums);
        return ans;
    }
    public void dfs(int cur, int[] nums) {
        ans.add(new ArrayList<>(t));
        if (cur == nums.length) {
            return;
        }
        for (int i = cur; i < nums.length; i++) {
            // 保留第一次相同的值，跳过同一层中的相同值
            if (i > cur && nums[i] == nums[i - 1]) {
                continue;
            }
            t.add(nums[i]);
            dfs(i + 1, nums);
            t.remove(t.size() - 1);
        }
    }
}
